#pragma once

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <set>
#include <vector>
#include <unordered_map>
#include <queue>
#include <memory>
#include <tuple>
#include <algorithm>

#include <utfcpp/utf8.h>
#include <nlohmann/json.hpp>

using std::pair;
using std::string;
using std::vector;
using std::unordered_map;
using std::set;
using std::shared_ptr;
using std::cout;
using std::endl;

// json类型
using Json = nlohmann::json;

// 三元组：候选词，最短编辑距离，在语料库中的出现次数
using candidateType = std::tuple<string, int, size_t>;

class CandidateWords
{
public:
    // 默认构造函数
    CandidateWords() = default;

    // 构造函数：传入词典库、索引库文件名
    CandidateWords(const string& cnDictFile, const string& cnIndexFile);  

    // 设置词典库文件、单字索引文件
    void setKeyWordsRecommender(const string &dictFile, const string &indexFile);

    // 根据用户输入内容，分析出相关候选词并返回 (以json格式)
    Json getCandidateWords(const string& input);

private:
    // 测试函数：打印词典、索引的前n行 (测试结束后设为private)
    void printCnDict(int lines);
    void printCnIndex(int lines);

private:
    // 将一个汉语词汇，分解成单个汉字，以vector存储
    shared_ptr<vector<string>> toSinoCharSequence(const string& sinoWord); 

private:
    vector<pair<string, size_t>> m_cnDict;          // 使用vector是为了保留“行号”的信息
    unordered_map<string, set<size_t>> m_cnIndex;
    // vector<pair<string, size_t>> enDict;
    // unordered_map<string, set<size_t>> enIndex;
};


// 计算两个序列之间的最短编辑距离
template<typename Sequence>
int minDistance(const Sequence& seq1, const Sequence& seq2) {
    int m=seq1.size(), n=seq2.size();
    if(m*n==0) return m+n; //有一个序列为空
    
    int dp[m+1][n+1];
    dp[0][0] = 0;
    for(int i=1; i<=m; i++) //第0列初始化 
        dp[i][0] = i;
    for(int j=1; j<=n; j++) //第0行初始化 
        dp[0][j] = j;
        
    for(int i=1; i<=m; i++) {
        for(int j=1; j<=n; j++) {
            if(seq1[i-1] == seq2[j-1])
                dp[i][j] = dp[i-1][j-1];
            else 
                dp[i][j] = std::min( dp[i-1][j-1], std::min(dp[i][j-1], dp[i-1][j]) ) + 1;
        }
    }
    return dp[m][n];
}
